package medium;

import data.ListNode;

import java.util.*;

/**
 * @author cmqzyd0700@163.com
 * @version 1.0
 * @since 2022/4/22 20:10
 */
public class No82_删除排序链表中的重复元素 {
    public static void main(String[] args) {
        Solution82 solution82 = new Solution82();
        ListNode head = new ListNode(1);
        head.add(1);
        //head.add(2);
        //head.add(5);
        //head.add(3);
        //head.add(3);
        ListNode listNode = solution82.deleteDuplicates(head);
        System.out.println(listNode);

    }
}

class Solution82 {
    public ListNode deleteDuplicates(ListNode head) {
        //来自官方思路,单指针
        if (head == null || head.next == null) {
            return head;
        }
        
        ListNode headCp = new ListNode(-1);
        headCp.next = head;
        ListNode pre = headCp;

        while (pre.next != null && pre.next.next != null) {
            if (pre.next.val == pre.next.next.val) {
                //相同时进来,判断最后删除结束的red(pre.next)位置是否重复
                int check = pre.next.val;
                //如果值一直相同,则一直删
                while (pre.next != null && pre.next.val == check) {
                    //一直删,当red(pre.next)到尾:则GG 1222222
                    pre.next = pre.next.next;
                }
            } else {
                pre = pre.next;
            }
        }
        return headCp.next;
    }
}



    //public ListNode deleteDuplicates(ListNode head) {
    //    //风骚的三指针,30%的理解率
    //
    //    if (head == null || head.next == null) {
    //        //说明链表长度0-1
    //        return head;
    //    }
    //    
    //    //定义pre,red,green指针,其中red,green比较指针
    //    //pre:指向单元素
    //    
    //    //定义头
    //    ListNode headCp = new ListNode(-1);
    //    headCp.next = head;
    //
    //    ListNode pre = headCp;
    //    ListNode red = head;
    //    ListNode green = head.next;
    //    while (green != null) {
    //        if (red.val != green.val) {
    //            //不同,则双双移动
    //            pre = red;
    //            red = red.next;
    //            green = green.next;
    //        } else {
    //            //相同,则移动到不同位置
    //            while (green != null && green.next != null && green.val == red.val) {
    //                red = red.next;
    //                green = green.next;
    //            }
    //
    //            //循环出来: green边界  green.val != red.val
    //            if (green.next == null) {
    //                //说明green是边界
    //                if (green.val == red.val) {
    //                    pre.next = null;
    //                    break;
    //                } else {
    //                    //344(r)5(g)
    //                    pre.next = green;
    //                }
    //            } else {
    //                //说明green不是边界且green.val != red.val
    //                //此时不能将pre直接指向green
    //                //why?: 由于green后面不知道是否相同
    //                pre.next = green;
    //                red = green;
    //                green = green.next;
    //            }
    //        }
    //    }
    //    return headCp.next;
    //}



    //public ListNode deleteDuplicates(ListNode head) {
    //    //定义TreeMap
    //    //(元素,是否重复)
    //    TreeMap<Integer, Boolean> treeMap = new TreeMap<>();
    //    //将链表元素进行wc
    //    while (head != null) {
    //        int val = head.val;
    //        if (treeMap.get(val) == null) {
    //            //如果没有这个val,说明第一次进来,那就是false
    //            treeMap.put(val, false);
    //        } else {
    //            treeMap.put(val, true);
    //        }
    //        head = head.next;
    //    }
    //
    //    ListNode res = new ListNode(-1);
    //    
    //    //遍历treeMap,摘出false的元素
    //    for (Map.Entry<Integer, Boolean> treeMapData : treeMap.entrySet()) {
    //        int data = treeMapData.getKey();
    //        boolean is重复 = treeMapData.getValue();
    //        if (!is重复) {
    //            //扔回ListNode
    //            addData(res, data);
    //        }
    //    }
    //    return res.next;
    //}
    //
    ////链表元素添加
    ////将data加入链表最后
    //public void addData(ListNode listNode, int data) {
    //    while (listNode != null && listNode.next != null) {
    //        listNode = listNode.next;
    //    }
    //    listNode.next = new ListNode(data);
    //    
    //}